
// 节点
template<typename DataType>
struct BiNode
{
    DataType data;
    BiNode *lchild, *rchild;
};


// 二叉排序树
class BiSortTree
{
public:
    BiSortTree(int a[], int n);     // 集合a[n] 的二叉排序树
    ~BiSortTree() {Release(root);};   // 和二叉链表的析构函数相同
    BiNode<int> * InsertBST(int x)  { return InsertBST(root, x); }  // 插入记录 x
    void DeleteBST(BiNode<int> *p , BiNode<int> *f);  // 删除f的左孩子p
    BiNode<int>*SearchBST(int k) { return SearchBST(root, k); } // 查找值为k的节点
private:
    BiNode<int>* InsertBST(BiNode<int>*bt , int x); // 插入
    BiNode<int>* SearchBST(BiNode<int>*bt , int k); // 查找
    void Release(BiNode<int>*bt); // 析构函数调用，同二叉链表
    BiNode<int>* root;            // 二叉排序树的根指针
};

// 构造函数
BiSortTree::BiSortTree(int a[], int n)
{
    root = nullptr;
    for(int i = 0; i<n; i++)
        root = InsertBST(root , a[i]);
}

BiSortTree::~BiSortTree()
{
}


// 查找函数
BiNode<int>* BiSortTree::SearchBST(BiNode<int>*bt , int k)
{
    if(bt = nullptr)
        return nullptr;
    if(bt->data == k)
        return bt;
    else if(bt->data > k)
        return SearchBST(bt->lchild , k);
    else
        return SearchBST(bt->rchild , k);
}

// 插入节点
BiNode<int>* BiSortTree::InsertBST(BiNode<int>*bt , int x)
{
    if(bt == nullptr)
    {
        BiNode<int> *s = new BiNode<int>; 
        s->data = x;  s->lchild = s->rchild = nullptr;
        bt = s;
        return bt;
    }
    else if (bt->data > x)
        bt->lchild = InsertBST(bt->lchild , x);
    else
        bt->rchild = InsertBST(bt->rchild , x);
}

// 删除节点
void BisortTree::DeleteBST(BiNode<int>*p , BiNode<int>*f)
{
    // 只有左子树
    if(p->lchild == nullptr && p->rchild == nullptr)
    {
        f->lchild = nullptr;
        delete p;
        return;
    }
    // p只有左子树
    if(p->rchild == nullptr)
    {
        f->lchild = p->lchild;
        delete p;
        return;
    }
    // p只有右子树
    if(p->lchild == nullptr)
    {
        f->lchild = p->rchild;
        delete p;
        return;
    }
    BiNode *par = p , *s = p->rchild;   // p的左右子树均不空
    while(s->lchild != nullptr)
    {
        par = s;
        s = s->lchild;
    }
    p->data = s->data;
    if(par == p)
        par->rchild = s->rchild;    // 特殊情况
    else
        par->lchild = s->rchild;
    delete s;
}